package com.xyhuo.leetcode.december;

/**
 * 搜索旋转排序数组Ⅱ
 * https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/
 *
 * @time 2023/12/29
 */
public class Search2 {

//    public static void main(String[] args) {
//        Search2 s = new Search2();
//        int[] nums = {5, 6, 7, 8, 9, 3, 4};
//        int[] num1 = {7, 8, 2, 3, 4, 5, 6};
//        int[] num2 = {1, 0, 1, 1, 1};
//        int[] num3 = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1};
//        int[] num4 = {1, 2, 1};
//        boolean search = s.search(num4, 2);
//        System.out.println(search);
//    }

    private void findTarget(int[] nums, int left, int right) {
        if (ans || left > right) {
            return;
        }
        while (left + 1 < right && nums[left + 1] == nums[left]) {
            left++;
        }
        while (right - 1 > left && nums[right - 1] == nums[right]) {
            right--;
        }
        int middle = (left + right) / 2;
        if (nums[middle] == target || nums[left] == target || nums[right] == target) {
            ans = true;
            return;
        }
        if (nums[middle] > nums[left]) {
            if (nums[middle] > target) {
                if (nums[left] <= target) {
                    findTarget(nums, left, middle - 1);
                }
                if (nums[right] >= target) {
                    findTarget(nums, middle + 1, right);
                }
            } else {
                findTarget(nums, middle + 1, right);
            }
        } else {
            if (nums[middle] < target) {
                if (nums[right] >= target) {
                    findTarget(nums, middle + 1, right);
                }
                if (nums[left] <= target) {
                    findTarget(nums, left, middle - 1);
                }
            } else {
                findTarget(nums, left, middle - 1);
            }
        }

    }

    private int target;

    private boolean ans = false;

    public boolean search(int[] nums, int target) {
        this.target = target;
        findTarget(nums, 0, nums.length - 1);
        return ans;
    }
}
